COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.CENT(Problems)
C00007 ENDMK
C⊗;
.CENT(Problems)
.begin "prob5"
.BEGIN CENTERIT;TABIT3(4,10,26);SELECT 1;
.GROUP
1  Use the following definition:
%3
.BOXA
\\match[k;m] <=\[null[k] → NO;
\\\ null[m] → NO;
\\\ eq[first[k];first[m]] → first[k];
\\\ %et%* → match[rest[k];rest[m]]]
.BOXB
%1
and evaluate:
\%2a.%3 match[(X);(X)]  \%2b.%3 match[(A B E);(J O E)]  
\%2c.%3 match[(F O O); (B A Z)]
.APART
%1

.GROUP
.BEGIN FILL;INDENT 0,17;
2.  Now write your own functions:

%2a.%3 among[x;y] <= ... : among%1 is to be a predicate; %3x%1 is an atom; %3y%1 is a list
of atoms.  %3among%1 is to return %ef%1 if %3x%1 is not found as an 
element of %3y%1; otherwise, %3among%* is to return %et%1.
.END

\e.g. %3among[A;(A B C)] = among[A;(C D E A)] = %et%*
\     among[A1;(A2 B2)] = %ef%*.
.APART
%1

.GROUP
.BEGIN FILL;INDENT 0,21;

%2b.%3 anywhere[x;y] <= ... : anywhere%1 is a predicate; %3x%1 is an atom; %3y%1 is an arbitrary
S-expr or list. %3anywhere%1 is to return %et%1 just in the case that %3x%1 appears somewhere in %3y%1.
.END

\e.g. %3anywhere[A;(A B C)] = anywhere[A;((A . B) . C)] = %et%*
\     anywhere[A;(B C D)] = %ef%*.
.APART
%1

.GROUP
.BEGIN INDENT 0,24;FILL;

%2c.%3 collectpair[z;x;y] <= ... : %3x%1 and %3y%* are atoms; 
%3z%* is an S-expression or list,
some of whose subexpressions, may begin %3(x#...)%* or %3(y#...)%*.  %3collectpair%*
is to return a dotted pair whose %3car%*-part is a list of all the occurrences
of %3(x#...)%*  and whose %3cdr%*-part is a list of all occurrences of %3(y#...)%*.
.END

\e.g. %3collectpair[((A 1) ((B . 2) (C A 4)));A;B] = (((A 1) (A 4)) . ((B . 2)))
%1
.APART

.GROUP
.BEGIN INDENT 0,16;FILL;

%2d.%3 pred[x] <= ... : x%1 is a positive integer. %3pred%* is a function, returning
the predecessor of its argument. The only arithmetic function you may use is %3add1%*.
.END

\e.g. %3pred[3] = 2;  pred[0] %1is undefined%*; 
\     pred[add1[x]] = x %1 for %3x %9≥%* 0.%1  

.apart
.GROUP
.BEGIN INDENT 0,18;FILL;

%2e.%3 signum[x] <= ... : x%1 is an integer. %3signum%1 returns %3NEGATIVE%1, %3ZERO%1,
or %3POSITIVE%1 depending on the sign of %3x%1. You may use %3add1%1 and %3sub1%1
but no comparision function other than %3eq%1.
.end
.apart
.GROUP
.pt18
.BEGIN INDENT 0,19;FILL;

%2f.%3 maxdepth[l] <= ... : l%1 is a list. This function is to find the maximum depth
of nesting of any element in %3l%1. Assume that %3l%1 is a strict list (see
{yon(P185)}); that is,
any sub-element is either atomic or is itself a strict list.
For example 
.begin center
.pt2
%3maxdepth[(#)]#=#0; maxdepth[(((B)#C)#A)]#=#3%1
.pt2
.end
.end
.end
.END "prob5"